package day;

public class P430 {
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }

        return solve(head, null);
    }

    //处理子结点
    private Node solve(Node head, Node next) {
        Node tmp = head;
        while (tmp.next != null) {
            if (tmp.child != null) {//子结点不为空
                Node newHead = solve(tmp.child, tmp.next);
                //插入
                tmp.child=null;
                Node newNext = tmp.next;
                newHead.prev = tmp;
                tmp.next = newHead;
                tmp = newNext;
            } else {//子结点为空
                tmp = tmp.next;
            }
        }
        //连接最后的结点
        if (next != null) {
            tmp.next = next;
            next.prev = tmp;
        }
        return head;
    }
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}